package tools;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Future;

import Triangulation.minimalityMetrics.MinimalityMetric;
import controller.DraftingHint;
import controller.Globals;
import controller.Notification;
import controller.NotificationCenter;
import datatypes.Edge;
import datatypes.FaceSet;
import datatypes.Vertex;
import datatypes.list.DoublyLinkedList;

/**
 * 
 * @author markessien, nils
 *
 */
public class FastLMTSkeletonCreator {
	public static class Logger {
		public long edgesCheckedForIntersection = 0;
		public int edgesWithoutLocalMinimum = 0;
		public int nonIntersectingEdges = 0;
		public double time;
		public double timePartA = 0;
		public double timePartB = 0;
		public double convexHullTime = 0;
		public double timeGenerateEdges = 0;
		public double timeGenerateTriangles = 0;
	}
	
	private Logger logger = new Logger();
	private MinimalityMetric metric;
	private NotificationCenter nc = NotificationCenter.defaultNotificationCenter();
	private boolean aborted = false;
	private FaceSet set;
	private int percent = 10;
	private boolean useBetaSkeleton = false;
	
	public FastLMTSkeletonCreator(MinimalityMetric metric, boolean useBetaSkeleton) {
		this.metric = metric;
		this.setUsesBetaSkeleton(useBetaSkeleton);
	}
	
	public void abort() {
		System.out.println("...aborting...");
		this.aborted = true;
		if (set != null) {
			set.abort();
		}
	}
	
	private void cleanupAfterAbort() {
		nc.postNotification(Notification.didTerminateTriangulator, this);
	}

	public Logger getLogger() {
		return logger;
	}
	/**
	 * The LMT-skeleton is a subgraph of the original graph. It contains all the
	 * edges that are in all possible minimum weight triangulations. After the LMT
     * is found, then the MWT can be calculated
	 * SEE A Large Subgraph of the Minimum Weight Triangulation page294
	 * 
	 * This function calculates the LMT.
	 * 
	 * 
	 * @param points The set of points
	 * @return The list with all edges within the skeleton in them
	 */
	public FaceSet calculateLMT(FaceSet set) {
		this.set = set;
		long start = System.currentTimeMillis();
		long startEdges = System.currentTimeMillis();
		set.generateEdges();
		logger.timeGenerateEdges += ((double)(System.currentTimeMillis() - startEdges))/1000;
		nc.postNotification(Notification.didProcessXPercent, percent++);
		if (set.size() <= 3) {
			set.edgesIn = set.getCandidateEdges();
			return set;
		}
		boolean edgeChanged = false;
		
		if (aborted) {
			System.out.println("abort 1");
			cleanupAfterAbort();
			return null;
		}
		
		long startTris = System.currentTimeMillis();
		set.generateTriangles();
		logger.timeGenerateTriangles += ((double)(System.currentTimeMillis() - startTris))/1000;
		nc.postNotification(Notification.didProcessXPercent, percent++);
		System.out.println("Triangle count:" + set.candidateTriangleCount());
		
		if (aborted) {
			System.out.println("abort 2");
			cleanupAfterAbort();
			return null;
		}
		
		// This method will look at the list of all potential edges ( set.getEdges() )
		// and it will add all edges that belong to the convex hull to the edgesIn list.
		// The convex hull is always part of any triangulation, and thus its edges are
		// in any minimum triangulation.
		long startCH = System.currentTimeMillis();
		List<Vertex> convexHullPoints = ConvexHullCreator.doJarvisMarch(set);
		
		// edgesIn is a list of edges that have been determined to be in
		// any locally minimal triangulation
		List<Edge> convexHull = ConvexHullCreator.getHullEdges(convexHullPoints, set.getCandidateEdges());
		for (Edge edge : convexHull) {
			set.edgesIn.add(edge);
			// Remove convex hull edges from our candidate list
			set.removeEdgeButLeaveTriangles(edge);
		}
		
		logger.convexHullTime += ((double)(System.currentTimeMillis() - startCH))/1000;
		nc.postNotification(Notification.didProcessXPercent, percent++);
		
		do {
			long startA = System.currentTimeMillis();
			edgeChanged = removeNonMinimalEdges(set);
			logger.timePartA += ((double)(System.currentTimeMillis() - startA))/1000;
//			System.out.println("part A done: " + percent);
			nc.postNotification(Notification.didProcessXPercent, percent++);
			
			
			if (aborted) {
				System.out.println("abort 3");
				cleanupAfterAbort();
				return null;
			}
			
			long startB = System.currentTimeMillis();
			if (reportNonIntersectingEdges(set)) {
//			if (reportNonIntersectingEdgesSingleThreaded(set, logger)) {
				edgeChanged = true;
			}
			logger.timePartB += ((double)(System.currentTimeMillis() - startB))/1000;
//			System.out.println("part B done: " + percent);
			nc.postNotification(Notification.didProcessXPercent, percent++);
			
			
			if (aborted) {
				System.out.println("abort 4");
				cleanupAfterAbort();
				return null;
			}
		} while (edgeChanged);
		logger.time = ((double)(System.currentTimeMillis() - start))/1000;
		
		System.out.println("Edges checked for intersection: " + logger.edgesCheckedForIntersection);
		System.out.println("Running time: " + logger.time);
		System.out.println("Running time Convex Hull: " + logger.convexHullTime);
		System.out.println("Running time generating edges: " + logger.timeGenerateEdges);
		System.out.println("Running time generating tris: " + logger.timeGenerateTriangles);
		System.out.println("Running time part A: " + logger.timePartA);
		System.out.println("Running time part B: " + logger.timePartB);
		System.out.println("");
		return set;
	}
	
	private Future<List<Edge>> nonIntersectingEdges(final FaceSet set, final int offset, int chunkSize, int  numberOfProcesses) {
		final List<Edge> edges = set.getCandidateEdges();
		final int maxIndex;
		if (offset + chunkSize > edges.size()) {
			maxIndex = edges.size();
		} else {
			maxIndex = offset + chunkSize;
		}
		ExecutorService executer = Globals.mainExecutor;
		Future<List<Edge>> future = executer.submit(new Callable<List<Edge>>() {
			public List<Edge> call() throws Exception {
				List<Edge> foundEdges = new ArrayList<Edge>();
				int edgesChecked = 0;
				
				for (int i = offset; i < maxIndex; i++) {
					Edge edge = edges.get(i);
					// IF e intersects no other edge in candEdges THEN add e to edgesIn
					boolean intersects = false;
					Edge otherEdge = edge.getFirstEdgeToCheckForIntersection();
					
					if (otherEdge == null && ! edge.hasStartedTraversingList) {
						/*
						 * This is the first time an edge is tested for intersection.
						 */
						edge.hasStartedTraversingList = true;
						otherEdge = set.getCandidateEdges().headNode();
					}
					
					while (otherEdge != null) {
						if (edge == otherEdge) {
							otherEdge = otherEdge.getNext();
							continue;
						}
						edgesChecked++;
						// Using negative precision value to prevent adjacent edges
						// from being detected as intersecting edges
						if (edge.intersects(otherEdge, -0.00001)) {
							intersects = true;
							/*
							 * Next time, we don't need to check for any of the edges
							 * up to the current intersectingEdge since all other edges
							 * checked before are known not to intersect. In order to
							 * start with this intersecting edge, we set the
							 * edge.firstEdgeToCheckForIntersection property:
							 */
							edge.setFirstEdgeToCheckForIntersection(otherEdge);
							break;
						}
						otherEdge = otherEdge.getNext();
					}
					
					
					if (intersects == false) {
						edge.setStatus(DraftingHint.IN);
							foundEdges.add(edge);
					}
					
					if (aborted) {
						System.out.println("abort 5");
						return null;
					}
				}
				synchronized (logger) {
					logger.edgesCheckedForIntersection += edgesChecked;
				}
				return foundEdges;
			}
		});
		return future;
	}
	
	/**
	 * @param set
	 * @param edgesIn
	 * @return
	 */
	private boolean reportNonIntersectingEdges(FaceSet set) {
		int numberOfCores = Runtime.getRuntime().availableProcessors();
//		numberOfCores = 1;
		boolean edgeChanged = false;
		Stack<Future<List<Edge>>> futureEdgesToBeRemoved = new Stack<Future<List<Edge>>>();
		DoublyLinkedList<Edge> edges = set.getCandidateEdges();
		/*
		 * edge indices have to be updated here because otherwise the indices would be
		 * updated on the first call to edges.get(index). Unfortunately that would
		 * happen inside the parallelized code and edges.updateIndices() is not synchronized!
		 */
		edges.updateIndices();
		if (edges.size() < numberOfCores*4) {
			// no multi-threading if the list of edges is small.
			futureEdgesToBeRemoved.push(nonIntersectingEdges(set, 0, edges.size(), 1));
		} else {
			int chunkSize = (edges.size() / numberOfCores) + 1;
			for (int i = 0; i < numberOfCores; i++) {
				futureEdgesToBeRemoved.push(nonIntersectingEdges(set, i*chunkSize, chunkSize, numberOfCores));
			}
		}
		
		// Wait...
		// Each time a future is done, add the non-intersecting edges to edgesIn, also
		// send a notification in order to trigger a redraw.
		List<List<Edge>> edgesToBeRemoved = new ArrayList<List<Edge>>();
		int nonIntersectingEdgesBefore = logger.nonIntersectingEdges;
		
		while (true) {
			for (int i = 0; i < futureEdgesToBeRemoved.size(); i++) {
				Future<List<Edge>> future = futureEdgesToBeRemoved.get(i);
				if (future.isDone()) {
					if (aborted) {
						System.out.println("abort 6");
						return false;
					}
					List<Edge> nonIntersectingEdges;
					try {
						nonIntersectingEdges = future.get();
						logger.nonIntersectingEdges += nonIntersectingEdges.size();
						set.edgesIn.addAll(nonIntersectingEdges);
						edgesToBeRemoved.add(nonIntersectingEdges);
						futureEdgesToBeRemoved.remove(i);
						break;
					} catch (InterruptedException e) {
						e.printStackTrace();
					} catch (ExecutionException e) {
						e.printStackTrace();
					}
				}
				
			}
			if (futureEdgesToBeRemoved.size() == 0) {
				// all futures have been done.
//				System.out.println("B: all futures done.");
				break;
			}
		}
		
		
		
		// since all edges have been tested, we can now safely
		// remove the non-intersecting edges from the set.
		for (List<Edge> nonIntersectingEdges : edgesToBeRemoved) {
				for (Edge edge : nonIntersectingEdges) {
					/*
					 * The triangles incident to this edge have to remain in the face set since they
					 * may still be needed by the other two edges to determine local minimality.
					 * contains
					 */
					set.removeEdgeButLeaveTriangles(edge); // remove edge from candEdges. Not specified in the paper
				}
		}
		
		edgeChanged = logger.nonIntersectingEdges != nonIntersectingEdgesBefore;
		if (edgeChanged) {
			nc.postNotification(Notification.didFindEdgeIn, set.edgesIn);
		}
		return edgeChanged;
	}
	
	/**
	 * @param set
	 * @param edgesIn
	 * @return
	 */
	@SuppressWarnings("unused")
	private boolean reportNonIntersectingEdgesSingleThreaded(FaceSet set, Logger logger) {
		boolean edgeChanged = false;
		DoublyLinkedList<Edge> edges = set.getCandidateEdges();
		
		
		for (Edge edge : edges) {
			// IF e intersects no other edge in candEdges THEN add e to the edgesIn
			boolean intersects = false;
			Edge otherEdge = edge.getFirstEdgeToCheckForIntersection();
			if (otherEdge == null) {
				otherEdge = set.getCandidateEdges().headNode();
			}
			
			
			while (otherEdge != null) {
				logger.edgesCheckedForIntersection++;
					// Using negative precision value to prevent adjacent edges
					// from being detected as intersecting edges
					
					if (edge != otherEdge && edge.intersects(otherEdge, -0.00001)) {
						intersects = true;
						edge.setFirstEdgeToCheckForIntersection(otherEdge);
						break;
					}
				otherEdge = otherEdge.getNext();
			}
			
			if (intersects == false) {
				edge.setStatus(DraftingHint.IN);
					set.edgesIn.add(edge);
					set.removeEdgeButLeaveTriangles(edge); // remove edge from candEdges. Not specified in the paper
					edgeChanged = true;
					logger.nonIntersectingEdges++;
			}
		}
		
		return edgeChanged;
	}
	
	
	/**
	 * @param set
	 * @return
	 */
	private boolean removeNonMinimalEdges(FaceSet set) {
		boolean edgeChanged = false;
		int edgeCountBefore = set.getCandidateEdges().size();
		for (Edge edge : set.getCandidateEdges()) {
			if ( ! edge.isDiagonalOfQuadrilateral() ) {
				set.removeEdge(edge);
				continue;
			}
			
			// If we find that this edge is not the local minimum for any possible
			// quadrilateral, this edge cannot be an element of an MWT. Hence we can
			// remove it from the candidates.
			if ( ! metric.localMinimumExistsForEdge(edge, set) ) {
				set.removeEdge(edge);
				logger.edgesWithoutLocalMinimum++;
			} else {
				edge.setStatus(DraftingHint.LOCALLY_MINIMAL);
			}
			if (aborted) {
//				System.out.println("abort 7");
				return false;
			}
		}
		
		edgeChanged = edgeCountBefore != set.getCandidateEdges().size();
		return edgeChanged;
	}
	
	public String getMetricName() {
		return metric.getName();
	}

	public boolean usesBetaSkeleton() {
		return useBetaSkeleton;
	}

	public void setUsesBetaSkeleton(boolean useBetaSkeleton) {
		this.useBetaSkeleton = useBetaSkeleton;
	}
}
